package likou.tanxin;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/16 05:58
 */
public class _995 {
    public static void main(String[] args) {
        System.out.println(minKBitFlips(new int[]{0, 0, 1, 0, 1, 1}, 2));
        System.out.println(minKBitFlips2(new int[]{0,0,0,1,0,1,1,0}, 3));
    }

    public static int minKBitFlips(int[] A, int K) {
        int start = 0;
        int end = A.length - 1;
        int daan = 0;
        boolean p = false;
        if (A.length != K) {
            while (start < A.length - K && start < end && end >= K) {
                while (end > start && start < A.length - K && A[start] == 1) {
                    start++;
                }
                int now = A[start];
                for (int i = start; i < K + start && now == 0; i++) {
                    A[i] = A[i] ^ 1;
                    p = true;
                }
                if (p) {
                    daan++;
                    p = false;
                }
                while (end > start && end > K - 1 && A[end] == 1) {
                    end--;
                }
                now = A[end];
                for (int i = end; i > end - K && now == 0; i--) {
                    A[i] = A[i] ^ 1;
                    p = true;
                }
                if (A[start] == 0) {
                    return -1;
                }
                if (p) {
                    daan++;
                    p = false;
                }
            }
        } else {
            int q = A[0];
            for (int i1 : A) {
                if (q != i1) {
                    return -1;
                }
            }
            return A[0] == 1 ? 0 : 1;
        }

        for (int i1 : A) {
            if (i1 == 0) {
                return -1;
            }
        }
        return daan;
    }


    /**
     * 牛逼！！！！！！！！！！！
     * @param A
     * @param K
     * @return
     */
    public static int minKBitFlips2(int[] A, int K) {
        int n = A.length;
        //开始翻转的位置的下标对应的值为1。
        int[] isFlipped = new int[n];
        int ans = 0;
        //flipped记录的是当前这个位置i不合规的值。
        int flipped = 0;

        for (int i = 0; i < n; i++) {
            if (i >= K) {
                //当前位置，当前被改为了flipped
                //如果超过改变的初始位置，则置为0，继续操作
                flipped ^= isFlipped[i - K];
            }
            //如果当前A[i]等于不合规的值，则就开始翻转
            if (A[i] == flipped) {
                //如果最后K-1个元素，还有不合规的，则直接返回-1，因为无法完成正常翻转
                if (i + K > n) {
                    return -1;// 如果没办法翻转整个子数组了，那么就不可行
                }
                //翻转一次，返回值++
                ans++;
                //当前位置开始翻转
                isFlipped[i] = 1;
                //flipped翻转
                flipped ^= 1;
            }
        }
        return ans;
    }
}
